package q646_findLongestChain;

import java.util.Arrays;
import java.util.Comparator;

public class Solution_1 {
    /*
    贪心的方式 应该按照右边界进行排序
    这样才能够使得每次左边的数组能够有更大的空间去选择
    要挑选最长数对链的第一个数对时，最优的选择是挑选第二个数字最小的，这样能给挑选后续的数对留下更多的空间。
    挑完第一个数对后，要挑第二个数对时，也是按照相同的思路，是在剩下的数对中，第一个数字满足题意的条件下，挑选第二个数字最小的。
    按照这样的思路，可以先将输入按照第二个数字排序，然后不停地判断第一个数字是否能满足大于前一个数对的第二个数字即可。
     */
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, Comparator.comparingInt(o -> o[1]));
        int cur = Integer.MIN_VALUE, ans = 0;
        for (int[] pair : pairs) {
            if (cur < pair[0]) {
                ++ans;
                cur = pair[1];
            }
        }
        return ans;
    }
}
